| 数据结构 静态顺序表（C语言） | 您所在的位置：网站首页 › 蛋壳 no pain no gain › 数据结构 静态顺序表（C语言） |
数据结构 静态顺序表（C语言）
|
数据结构 静态顺序表
一、线性表 1.数据结构中，线性结构习惯称为线性表，线性表是最简单也是最常用的一种数据结构。 2.线性表可以表示为：（A_1,A_2,A_3,…,A_N）,其中，A_i（i=1,2,…,n）是线性表的数据元素，也称为线性表的一个节点，同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象。数组、矩阵、向量等都是线性表。大小为0的表为空表。 3.对于除空表外的任何表，我们说A_(i+1)后继A_i并且称A_(i-1)（i1）。表中的第一个元素是A_1，而最后一个元素是A_N。不定义A_1的前驱元，也不定义A_N的后继元。元素A_i在表中的位置为i。 二、顺序表 1.线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。（注意：结点序号与数组下标不同） 三、静态顺序表的存储结构定义： #define SIZE 20 typedef struct node{ char name[SIZE]; //姓名 char sex[SIZE]; //性别 int age; //年龄 }Node; //用结构体Node作为顺序表元素的数据类型 typedef struct list{ Node elem[SIZE]; //线性表占用的数组空间 int last; //保存顺序表最后一个元素的下标,空表时置为-1 }List;该定义中通过typedef为某一类型自定义名称。用Node作为struct node的别名（这样做更加通用），如果以后需要其他数据形式的静态顺序表，可以重新定义Node类型。用List作为struct list的别名，若有List L;则表示创建了一个静态顺序表。若有List * L;则表示创建了一个指向静态顺序表的指针。 四、静态顺序表的初始化： 初始化静态顺序表，将表的last成员置为-1。 void InitList(List * L) //形参：指向List类型的指针，由于该函数不修改顺序表，使用const修饰符对指针所指向的内容进行保护 { L->last=-1; //顺序表初始化为空，L的last成员置为-1 }五、静态顺序表的查找： ①按序号查找GetData(L, i)：要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]。 Node GetData(const List * L,int i) //形参：1.指向List类型的指针，由于该函数不修改顺序表，使用const修饰符对指针所指向的内容进行保护 2.第i个数据元素 { Node temp; //定义一个Node类型的变量temp,用于存储待查的数据元素 temp=L->elem[i-1]; //将线性表L中第i个数据元素赋予temp return temp; //将存储待查数据元素的temp返回 }②按内容查找Locate(L, e)：要求查找线性表L中与给定值e相等的数据元素。若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”-1。 int Locate(const List * L,const char name[]) //形参:1.指向List类型的指针，由于该函数不修改顺序表，使用const修饰符对指针所指向的内容进行保护 2.待查找的值(形式自定义) { int i=0; //变量i用作数组下标 while((ilast)&&strcmp(L->elem[i].name,name)!=0) //下标在边界范围内，未找到待查值时做循环 i++; if(ilast) //若找到待查元素，则返回该元素在表中的序号(不是下标) return i+1; else //否则，返回“空序号”-1 return -1; }六、静态顺序表的插入： 算法描述：用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将原表中位置n,n-1,…,i上的元素，依次后移到位置n+1,n,…,i+1上，空出第i个位置，然后在该位置上插入新元素。当i=n+1时，是指在线性表的末尾插入新元素，所以无需移动其余元素，直接将新元素插入表的末尾即可。插入前表长n=L->last+1，i的合法范围是 1≤i≤L->last+2（注意：结点序号与数组下标不同，注意在表末尾插入的情况，i>L->last+2） bool InsList(List * L,int i,Node node) //形参:1.指向List类型的指针 2.插入位置，顺序表第i个结点 3.顺序表的元素 { int j; if(L->last>=SIZE-1) //判断顺序表是否已满 { printf("List is full,can't insert!"); return false; } if((iL->last+2)) //判断插入的位置是否合法。 { printf("Insert position illegal!"); return false; } for(j=L->last;j>=i-1;j--) //从顺序表的最后一个元素的下标开始，查找第i个位置 L->elem[j+1]=L->elem[j]; //将第i个位置的元素以及其后元素挨个向后移，空出第i个位置 L->elem[i-1]=node; //为第i个位置元素赋值 L->last++; //更新last为现顺序表最后一个元素的下标 return true; }
七、静态顺序表的删除： 算法描述：用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此当需要删除第i个元素时，必须将原表中位置在i+1,i+2,…,n-1,n上的结点，依次前移到位置为i,i+1,…,n-1(其中n为L的表长度)。在顺序表L中删除第i个数据元素，函数返回删除成功与否的标志。并用指针参数返回已删除元素的值。i的合法取值为1≤i≤L.last+1。（注意：结点序号与数组下标不同） bool DelList(List * L,int i,Node * node) //形参:1.指向List类型的指针 2.删除位置，顺序表第i个结点 3.指向Node类型的指针，用于带出被删元素的值 { int j; if(L->last==-1) //判断顺序表是否为空 { printf("List is empty, can't delete!"); return false; } if((iL->last+1)) //判断删除位置是否合法。 { printf("Remove location illegal!"); return false; } *node=L->elem[i-1]; //将被删元素的值通过指针node返回 for(j=i;jlast;j++) //从被删位置开始，做循环 L->elem[j-1]=L->elem[j]; //将被删位置其后元素挨个往前移 L->last--; //更新last为现顺序表最后一个元素的下标 return true; }
八、静态顺序表的输出： 通过循环遍历数组下标，输出数组的每一个元素。（或者直接通过下标输出想要的元素） void output(const List * L) //形参：1.指向List类型的指针，由于该函数不修改顺序表，使用const修饰符对指针所指向的内容进行保护 { int i; for(i=0;ilast+1;i++) //遍历数组下标，输出数组的每一个元素（输出形式自定义） { printf("name:%-10s sex:%-10s age:%-10d\n",L->elem[i].name,L->elem[i].sex,L->elem[i].age); } }九、总结： 1.静态顺序表的大小在编译时确定，对静态顺序表的删除和插入是对其元素进行，而不是其存储空间的删除和插入，因此静态顺序表的大小在进行删除和插入操作后不会改变。（表长是指静态顺序表的实际使用空间的大小） 2.对于静态顺序表的插入和删除，若在第i个位置插入元素，需要将第i个位置的元素及其后元素后移一个位置以空出空间来，而删除第i个位置的元素，则需要将第i个位置的后方元素前移一个位置。因此这两种操作的时间复杂度为O(N)。平均来看，这两种操作都需要移动表中一半的元素，因此仍然需要线性时间。（静态顺序表在做这两种操作时还需要注意表的大小，防止出现位置不合法，而动态顺序表在插入元素时可通过为表进行空间分配增加表的大小）。 3. 对于静态顺序表的查找，若按序号查找，则时间复杂度为O(1)。若按值查找，则需要将待查元素与表中每一个元素进行比较，直到找到或者遍历整个数组却找不到元素，此操作的时间复杂度为O(N)。 十、静态顺序表的合并： 设表LC是一个空表，指针k指向LC当前元素； 设两个指针i、j分别指向表LA和LB中的当前元素； 若LA.elem[i]>LB.elem[j]，则将LB.elem[j]插入到表LC中，并将j后移一个元素；k后移一个元素； 若LA.elem[i]≤LB.elem[j]，则将LA.elem[i]插入到表LC ，并将i后移一个元素；k后移一个元素； 重复该操作，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素依次放到表LC中。 #include #define SIZE 100 typedef int Node; typedef struct list{ Node elem[SIZE]; //线性表占用的数组空间 int last; //保存顺序表最后一个元素的下标,空表时置为-1 }List; void output(List * L); void InitList(List * L); void MergeList(List * LA,List * LB,List * LC); int main() { int a,b; List LA,LB,LC; InitList(&LA); InitList(&LB); InitList(&LC); printf("请输入按升序排列的一列整数,以#号结束:"); while(scanf("%d",&a)==1) { LA.last++; LA.elem[LA.last]=a; } printf("表A中的元素为:\n"); output(&LA); getchar(); //吸取输入序列中的#号 printf("\n请输入按升序排列的另一列整数,以#号结束:"); while(scanf("%d",&b)==1) { LB.last++; LB.elem[LB.last]=b; } printf("表B中的元素为:\n"); output(&LB); MergeList(&LA,&LB,&LC); printf("\n表A与表B合并后,按升序排列为:\n"); output(&LC); return 0; } void InitList(List * L) { L->last=-1; } void output(List * L) { int i; for(i=0;ilast+1;i++) { printf("%d\t",L->elem[i]); } } void MergeList(List * LA,List * LB,List * LC) { int i,j,k; i=0; j=0; k=0; //i,j,k分别表示LA,LB,LC当前元素的下标 while(ilast&&jlast) //将LA与LB中的较小元素放入LC中 { if(LA->elem[i]elem[j]) { LC->elem[k]=LA->elem[i]; i++; k++; } else { LC->elem[k]=LB->elem[j]; j++; k++; } } while(ilast) //将LA中的剩余元素放入LC中 { LC->elem[k]=LA->elem[i]; i++; k++; } while(jlast) //将LB中的剩余元素放入LC中 { LC->elem[k]=LB->elem[j]; j++; k++; } LC->last=LA->last+LB->last+1; }
十一、样例： #include #include #include #define SIZE 20 typedef struct node{ char name[SIZE]; //姓名 char sex[SIZE]; //性别 int age; //年龄 }Node; typedef struct list{ Node elem[SIZE]; //线性表占用的数组空间 int last; //保存顺序表最后一个元素的下标,空表时置为-1 }List; void InitList(List * L); void output(const List * L); Node GetData(const List * L,int i); bool InsList(List * L,int i,Node node); bool DelList(List * L,int i,Node * node); int Locate(const List * L,const char name[]); int main() { List L; //创建一个顺序表L int i,j,k,l,n,m; char name[SIZE]; //用于按值查找算法 Node temp1; //用于按序号查找算法 Node node1; //用于插入算法 Node node2; //用于删除算法，保存被删元素的值 InitList(&L); printf("请输入信息的个数:"); scanf("%d",&n); getchar(); //处理scanf()遗留在缓冲区的换行符 for(i=0;i L->last=-1; } Node GetData(const List * L,int i) { Node temp; temp=L->elem[i-1]; return temp; } int Locate(const List * L,const char name[]) { int i=0; while((ilast)&&strcmp(L->elem[i].name,name)!=0) i++; if(ilast) return i+1; else return -1; } bool InsList(List * L,int i,Node node) { int j; if(L->last>=SIZE-1) { printf("List is full,can't insert!"); return false; } if((iL->last+2)) { printf("Insert position illegal!"); return false; } for(j=L->last;j>=i-1;j--) L->elem[j+1]=L->elem[j]; L->elem[i-1]=node; L->last++; return true; } bool DelList(List * L,int i,Node * node) { int j; if(L->last==-1) { printf("List is empty, can't delete!"); return false; } if((iL->last+1)) { printf("Remove location illegal!"); return false; } *node=L->elem[i-1]; for(j=i;jlast;j++) L->elem[j-1]=L->elem[j]; L->last--; return true; } void output(const List * L) { int i; for(i=0;ilast+1;i++) { printf("name:%-10s sex:%-10s age:%-10d\n",L->elem[i].name,L->elem[i].sex,L->elem[i].age); } }输出结果： |
2.地址的计算：线性表中第一个元素的存储地址（基地址）和表中每个元素所占存储单元的多少，就可以计算出线性表中任意一个数据元素的存储地址，从而实现对顺序表中数据元素的随机存取。 设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为Loc（a_1）,则第i个元素的地址Loc（a_i）：Loc（a_i）=Loc（a_1）+（i-1）*k
【本文地址】